package ru.qiwi.security;
/********** ����� ���������� **********/


import java.io.IOException;
import java.util.Random;


/**
 * ���������������� ��� ���� ����� RSA
 */
public class RSAKey
{


	// Debugging methods and variables
	// -------------------------------------------------------------------------

	//private static final PrintWriter err = new PrintWriter(System.out, true);

	// Constants and variables
	// -------------------------------------------------------------------------

//   private static final int DEFAULT_CERTAINTY = 20; // XXX is this a good value?
/*   private static final ru.eport.handler.BigInteger ZERO = ru.eport.handler.BigInteger.ZERO;
   private static final ru.eport.handler.BigInteger ONE = ru.eport.handler.BigInteger.ONE;*/
	private static final BigInteger TWO = BigInteger.valueOf( 2 );

	/**
	 * The first SMALL_PRIME primes: Algorithm P, section 1.3.2, The Art of
	 * Computer Programming, Donald E. Knuth.
	 */
	private static final int SMALL_PRIME_COUNT = BigInteger.primes.length;
	private static BigInteger[] SMALL_PRIME;

	// Constructor(s)
	// -------------------------------------------------------------------------

	/**
	 * Trivial constructor to enforce Singleton pattern.
	 */
	/*private Prime()
	{

	} */

	// Class methods
	// -------------------------------------------------------------------------


	static void makeSmallPrimes()
	{
		if( SMALL_PRIME != null )
		{
			return;
		}

		SMALL_PRIME = new BigInteger[ SMALL_PRIME_COUNT];


		SMALL_PRIME[0] = TWO;
/*      int N = 3;
      int J = 0;
      int prime;*/

		//���������� ������� �����������
		for( int i = 0; i < SMALL_PRIME_COUNT; i++ )
		{
			SMALL_PRIME[i] = BigInteger.valueOf( BigInteger.primes[i] );
		}
/*      P2: while (true) {
         SMALL_PRIME[++J] = ru.eport.handler.BigInteger.valueOf(N);
         if (J >= SMALL_PRIME_COUNT - 1) {
            break P2;
         }
         P4: while (true) {
            N += 2;
            P6: for (int K = 1; true; K++) {
               prime = SMALL_PRIME[K].intValue();
               if ((N % prime) == 0) {
                  continue P4;
               } else if ((N / prime) <= prime) {
                  continue P2;
               }
            }
         }
      }*/
	}


	static void deleteSmallPrimes()
	{
		SMALL_PRIME = null;

	}

	/**
	 * �� ������ ���� ����������� Euler Criterion ��� ����� 2.
	 * Euler Criterion ����������, ��� a ^ ((p-1) / 2) == J(a, p) ���
	 * ��������� �������� p, ���
	 * J(a, p) == 1, ���� ���������� x : x * x == a (mod p), � J(a, p) == -1,
	 * ���� �� ���������� ������ x. �� ����� ������ �������, ���
	 * J(a, p) == 1 ���� p == +/- 1 (mod 8) � J(a, p) == -1, ���� p == +/-3 (mod 8)
	 * <p/>
	 * ������������ ���� ����, ��� a^(p-1) == 1 mod p, ���� p - �������
	 * � �� ����� a. ���� p-1 = b * 2^k, ��� b - ��������, �� ��������
	 * ��������� �������� (k > 0).
	 * 1. ��������� a^b mod p. ���� a^b == +/- 1 mod p, ��
	 * a^(p-1) = a^(b * 2^k) = (a^b)^(2^k) = ((a^b)^2)^(2*(k-1)) =
	 * = 1^(2*(k-1)) = 1 mod p; (k - 1 >= 0);
	 * 2. � ��������� ������ �������� (a^b) � ������� �� ����� (k-1)
	 * ����. ���� ���������� -1, �� ��������� ������� ���� 1 �, ��������,
	 * ����� �������. ���� ���������� 1, �� ��� ������, ��� p - �� �������
	 * (a^2 == 1 mod p <=> (a-1)(a+1) == 1 mod p). �.�. ���� �� ����������
	 * ���� ���� 1 (��� -1) � �������� ���������� �����, ���� ����� p - ��
	 * �������. ���� �� -1 �� ���� ���������� �� (k-1) ���, �� 1 �� �����
	 * ���������� �� ��������� ���� (����, ��� ����������� �����,
	 * p - �� �������).
	 *
	 * @param w ����� ��� ��������
	 * @return true, ���� �������������, ����� false
	 * @throws InterruptedException ���������, ���� ���������� ���� ��������, ��������, ��-�� ����, ��� � ������� ��������� ������ ���������
	 * ������ ��������
	 */

	static boolean passEulerCriterion( final BigInteger w ) throws InterruptedException
	{
		BigInteger wMinusOne = w.subtractOne();
		BigInteger e = w.subtractOne();
		BigInteger A;

		int lowBits = e.getLowBitsMask( 7 );  // ��� ������� ����
		int j;
		int b;
		int start = 1;

		if( lowBits != 0 ) // ���� ��� ��������� ���� - �� ����
		{
            e.setShiftRight( 1 );
			A = TWO.modPow( e, w );
			if( lowBits == 6 )
			{ //w == 7 (mod 8)
				if( !A.isOne() )
				{
					return false;//should be one
				}
				b = 1;
			}
			else
			{ //lowBits == 4 || lowBits == 2 , w == +/-3 (mod 8),
				if( !A.equalsto( wMinusOne ) ) //should be A == -1
				{
					return false;
				}
				if( lowBits != 4 ) //lowBits == 2
				{
					b = 1;
				}
				else
				{
					b = 2;
					e.setShiftRight( 1 ); //odd for strong tests
				}
			}
		}
		else
		{ //w == 1 (mod 8)
			e.setShiftRight( 2 );
			A = TWO.modPow( e, w );
			if( A.isOne() )
			{
				start = 0; //�������� � ������� ����� �� ���������� ������ �� 1
			}
			else
			{
				//���� �������� �� -1, �� ���� 2^((w-1)/2) != 1,
				//���� ���� x != +/-1, x^2 == 1 (mod w). � ����� �������
				//w - �� �������
				if( !A.equalsto( wMinusOne ) )
				{
					return false;
				}
			}
			b = e.getLowestSetBit();
			e.setShiftRight( b );
			b += 2;
		}

		for( int i = start; i < 13; i++ )
		{
			A = SMALL_PRIME[i].modPow( e, w );
			//if p is prime then for any a != 0 (mod p) => a^(p-1) = 1 (mod p)
			if( A.isOne() || A.equalsto( wMinusOne ) )
			{
				continue;
			}
			for( j = 0; j < b - 1; j++ )
			{
				A = A.modPow( TWO, w );
				if( A.equalsto( wMinusOne ) )
				{
					break;
				}
				//if a^2 = 1 mod w have solution not 1 or -1,
				//then w is not prime
				if( A.isOne() )
				{
					return false;
				}
			}
			if( j == b )
			{
				return false;
			}
		}
		return true;
	}


	/**
	 * <p>This implementation does not rely solely on the Miller-Rabin strong
	 * probabilistic primality test to claim the primality of the designated
	 * number. It instead, tries dividing the designated number by the first 1000
	 * small primes, and if no divisor was found, invokes a port of Colin Plumb's
	 * implementation of the Euler Criterion, then tries the Miller-Rabin test.</p>
	 *
	 * @param w						 the integer to test.
	 //* @param certainty		 the certainty with which to compute the test.
	 //* @param doMillerRabin if <code>true</code> and the designated integer was
	 //*                      already found to be a probable prime, then also do a Miller-Rabin test.
	 * @return <code>true</code> if the designated number has no small prime
	 *         divisor passes the Euler criterion, and optionally a Miller-Rabin test.
	 * @throws InterruptedException ���������, ���� ���������� ���� ��������, ��������, ��-�� ����, ��� � ������� ��������� ������ ���������
	 * ������ ��������
	 */
	static boolean isProbablePrime( BigInteger w ) throws InterruptedException
	{
//      int certainty = DEFAULT_CERTAINTY;
		// Nonnumbers are not prime.
/*      if (w == null) {
         return false;
      }

      // eliminate trivial cases when w == 0 or 1
      if (w.isZero() || w.isOne() ) {
         return false;
         never check this
      }

      // Test if w is a known small prime.
      // we should not test this, because numbers are quite big
/*      for (int i = 0; i < SMALL_PRIME_COUNT; i++) {
                  if (w.equalsto(SMALL_PRIME[i])) {
            return true;
         }
      }*/

		//don't check prime 2 (this is guaranted by ru.eport.handler.RSAKey)
		for( int i = 1; i < SMALL_PRIME_COUNT; i++ )
		{
			if( w.divides( BigInteger.primes[i] ) )
			{
				return false;
			}
		}

		// Do a check with Fermat's little theorem.
//       if (passFermatLittleTheorem(w, certainty)) {
//          if (DEBUG && debuglevel > 4) {
//             debug(w.toString(16)+" passes Fermat's little theorem...");
//          }
//       } else {
//          if (DEBUG && debuglevel > 4) {
//             debug(w.toString(16)+" fails Fermat's little theorem. Rejected...");
//          }
//          return false;
//       }

		//      Euler's criterion.
		//      System.out.println(".");
		if( passEulerCriterion( w ) )
		{
			return true;
		}
		//       System.out.println("...");
		return false;

		// Miller-Rabin probabilistic primality test.
		/*  if (passMillerRabin(w, certainty)) {
						 if (DEBUG && debuglevel > 4) {
								debug(w.toString()+" passes Miller-Rabin PPT...");
						 }
					} else {
						 if (DEBUG && debuglevel > 4) {
								debug(w.toString()+" fails Miller-Rabin PPT. Rejected...");
						 }
						 return false;
					} */

	}









	/**
	 * ���������, �������������� �������� ��������� ����� (������ + ����������), � DER-�������. ����������� ��� ����� � 1024 ���.
	 */
	//public static final byte[] PUB_KEY1024_DER_HEADER = new byte[]{0x30, ( byte ) 0x81, ( byte ) 0x9F, 0x30, 0x0D, 0x06, 0x09, 0x2A,
	//																													 ( byte ) 0x86, 0x48, ( byte ) 0x86, ( byte ) 0xF7, 0x0D, 0x01, 0x01, 0x01,
	//																													 0x05, 0x00, 0x03, ( byte ) 0x81, ( byte ) 0x8D, 0x00, 0x30, ( byte ) 0x81,
	//																													 ( byte ) 0x89, 0x02, ( byte ) 0x81, ( byte ) 0x81, 0x00};

	/**
	 * ���������, �������������� �������� ��������� ����� (������ + ����������), � DER-�������. ����������� ��� ����� � 512 ���.
	 */
	static final byte[] PUB_KEY512_DER_HEADER = new byte[]{
            0x30, 0x5C, 0x30, 0x0D, 0x06, 0x09, 0x2A, ( byte ) 0x86,
    		0x48, ( byte ) 0x86, ( byte ) 0xF7, 0x0D, 0x01, 0x01, 0x01, 0x05,
			0x00, 0x03, 0x4B, 0x00, 0x30, 0x48, 0x02, 0x41, 0x00
    };

	/**
	 * ��������� ��������� ����� � DER �������
	 */
	static final byte[] PUB_KEY_DER_HEADER = PUB_KEY512_DER_HEADER;
	final int BIT_LENGTH;
	final int BYTE_LENGTH;
	static final byte exp_bytes[] = {0x00, 0x01, 0x00, 0x01};
	static final BigInteger pub = new BigInteger( exp_bytes );
	static final int EXP_VALUE = 65537; //int value of the exp_bytes;


	BigInteger mod, priv;

	RSAKey( BigInteger mod, BigInteger priv )
	{
		this.mod = mod;
		this.priv = priv;
		BIT_LENGTH = this.mod.bitLength();
		BYTE_LENGTH = BIT_LENGTH / 8;
	}

	// ����������
//	byte[] encrypt( byte srcMessage[] ) throws InterruptedException
//	{
//		//DEBUG: System.err.println("Encrypting"); //DEBUG:
//		final int SRC_MESSAGE_LENGTH = srcMessage.length;
//		byte res[];
//		BigInteger e = priv == null ? pub : priv;
//		/*
//		���������� �������� ����, ������������ � ����� �������������� �����
//		 */
//		final int BLOCK_SIZE = BYTE_LENGTH - 1;
//		int blocks = SRC_MESSAGE_LENGTH / BLOCK_SIZE;
//		if( SRC_MESSAGE_LENGTH % BLOCK_SIZE != 0 )
//		{
//			blocks++;
//		}
//		res = new byte[blocks * BYTE_LENGTH];
//		//for( int i = 0; i < res.length; i++ )
//		//{
//		//	res[i] = 0;
//		//}
//
//		byte blk[] = new byte[BYTE_LENGTH + 1];
//
//		int offset = 0;
//		int pos = 0;
//		//DEBUG: System.err.println("Before loop"); //DEBUG:
//		while( offset < SRC_MESSAGE_LENGTH )
//		{
//			//DEBUG: System.err.println(offset); //DEBUG:
//			//blk[0] = 0; // ����� �������������� �������� ������������� �����
//			blk[1] = 1; // Magic + �������������, ��� � ����� �� ������ ��������� ������ ������
//			//for( int i = 2; i < blk.length; i++ )
//			//{
//			//	blk[i] = 0;
//			//}
//
//			int tail = SRC_MESSAGE_LENGTH - offset;
//			if( tail > BLOCK_SIZE )
//			{
//				tail = BLOCK_SIZE;
//			}
//			System.arraycopy( srcMessage, offset, blk, blk.length - BLOCK_SIZE, tail );
//			offset += BLOCK_SIZE;
//
//			//int sum = 0, sum2 = 0;
//			//for( int i = 2; i < blk.length; i++ )
//			//{
//			//	sum += blk[i];
//			//	sum2 += blk[i] < 0 ? -blk[i] : blk[i];
//			//}
//			BigInteger src = new BigInteger( blk );
////			src.out();
////			e.out();
////			mod.out();
//			BigInteger dst = src.modPow( e, mod );
////			dst.out();
//			byte r[] = dst.toByteArray();
//			if( r.length < BYTE_LENGTH )
//			{
//				int l = BYTE_LENGTH - r.length;
//				for( int i = 0; i < l; i++ )
//				{
//					res[pos++] = 0;
//				}
//				System.arraycopy( r, 0, res, pos, r.length );
//				pos += r.length;
//			}
//			else
//			{
//				int l = r.length - BYTE_LENGTH;
//				System.arraycopy( r, l, res, pos, BYTE_LENGTH );
//				pos += BYTE_LENGTH;
//			}
//			try
//			{
//				Thread.sleep( 20 );
//			}
//			catch( InterruptedException ignored)
//			{
//
//			}
//		}
//		System.gc();
//		return res;
//	}

//	byte[] decrypt( byte b[] ) throws IOException, InterruptedException
//	{
//		if( b.length % BYTE_LENGTH != 0 )
//		{
//			throw new IOException( "Decrypt: bad length:" + b.length );
//		}
//		BigInteger e = priv == null ? pub : priv;
//
//		int blksize = BYTE_LENGTH - 1;
//		int blocks = b.length / BYTE_LENGTH;
//		byte res[] = new byte[blocks * blksize];
//		byte buff[] = new byte[BYTE_LENGTH + 1];
//		buff[0] = 0;
//		int offset = 0;
//		int pos = 0;
//		while( offset < b.length )
//		{
//			System.arraycopy( b, offset, buff, 1, BYTE_LENGTH );
//			offset += BYTE_LENGTH;
//			BigInteger src = new BigInteger( buff );
//			BigInteger dst = src.modPow( e, mod );
//			byte r[] = dst.toByteArray();
//			// ������ ���� �� ������ ����� �����!
//			if( r.length < BYTE_LENGTH )
//			{
//				throw new IOException( "Decrypt: bad blocks length:" + r.length );
//			}
//			// ��������� �������� ����
//			int sig = r.length - BYTE_LENGTH;
//			// ��������� magic
//			if( r[sig] != 1 )
//			{
//				throw new IOException( "Decrypt: bad magic:" + r[sig] );
//			}
//			System.arraycopy( r, sig + 1, res, pos, blksize );
//			pos += blksize;
//			try
//			{
//				Thread.sleep( 20 );
//			}
//			catch( InterruptedException exInterrupt )
//			{
//
//			}
//		}
//		System.gc();
//		return res;
//	}

	/**
	 * ���������� ������� ������. ������ ��� ������ ���� � ��������� � ������� ���������� ������, ������� ���������� ��� ������� ��
	 * ���������������� ���������
	 *
	 * @param b ������ ��� �������
	 * @return �������
	 * @throws InterruptedException ��� ������ ���������� ��������
	 */
	byte[] sign( byte b[] ) throws InterruptedException
	{
		if( b.length != BYTE_LENGTH - 1 )
		{
			throw new IllegalArgumentException( "Wrong size of input data: " + b.length + ". Must be: " + ( BYTE_LENGTH - 1 ) );
		}
		if( priv == null )
		{
			throw new IllegalStateException( "Sign: no private part" );
		}
		BigInteger src = new BigInteger( b );
		BigInteger sign = src.modPow( priv, mod );
		System.gc();
		return sign.toByteArray();
	}


	// ������������  �����
	byte[] serialize() throws IOException
	{
//		int i, j;
		byte b[];
		byte buff[] = new byte[BYTE_LENGTH * 2];
		b = mod.toByteArray();
		if( b.length < BYTE_LENGTH )
		{
			throw new IOException( "RSA: mod too small (" + b.length + ')' );
		}
		if( b.length > BYTE_LENGTH + 1 )
		{
			throw new IOException( "RSA: mod too big (" + b.length + ')' );
		}
		System.arraycopy( b, b.length - BYTE_LENGTH, buff, 0, BYTE_LENGTH );

		b = priv.toByteArray();
		if( b.length < BYTE_LENGTH )
		{
			throw new IOException( "RSA: exp too small (" + b.length + ')' );
		}
		if( b.length > BYTE_LENGTH + 1 )
		{
			throw new IOException( "RSA: exp too big (" + b.length + ')' );
		}
		System.arraycopy( b, b.length - BYTE_LENGTH, buff, BYTE_LENGTH, BYTE_LENGTH );
		return buff;
	}

	// �������������� �����
	public static RSAKey restore( byte b[], int offset, int keyLength ) throws IOException
	{
		int bytes = keyLength / 8;
		if( b.length - offset < bytes * 2 )
		{
			throw new IOException( "Bad key size!!!" );
		}
		byte buff[] = new byte[bytes + 1];
		System.arraycopy( b, offset, buff, 1, bytes );
		BigInteger m = new BigInteger( buff );
		System.arraycopy( b, offset + bytes, buff, 1, bytes );
		BigInteger p = new BigInteger( buff );
		return new RSAKey( m, p );
	}

	/**
	 * @return ��������������� �������� ����. ������, ������������� ������ ���������� � ���� ������� ����
	 * @throws IllegalStateException ���� ���������� ���� � ������� �� ��������� � �������� ����� ���������� � ������
	 */
	byte[] serializePublic()
	{
		byte b[] = mod.toByteArray();
		if( b.length == BYTE_LENGTH )
		{
			return b;
		}
		else if( b.length < BYTE_LENGTH )
		{
			throw new IllegalStateException( "RSA: mod too small (" + b.length + ')' );
		}
		else
		//if( b.length > BYTE_LENGTH + 1 )
		{
			throw new IllegalStateException( "RSA: mod too big (" + b.length + ')' );
		}
		//byte buff[] = new byte[BYTE_LENGTH];
		//System.arraycopy( b, b.length - BYTE_LENGTH, buff, 0, BYTE_LENGTH );
		//return buff;
	}

	// �������������� ���������� �����
//	static RSAKey restorePublic( byte b[], int offset, int keyLength ) throws IOException
//	{
//		int bytes = keyLength / 8;
//
//		if( b.length - offset < bytes )
//		{
//			throw new IOException( "Bad key size!!!" );
//		}
//		byte buff[] = new byte[bytes + 1];
//		System.arraycopy( b, offset, buff, 1, bytes );
//		BigInteger m = new BigInteger( buff );
//		return new RSAKey( m, null );
//	}

    /**************************   for show progress   **************************
    private static final String xxx = ".......................";
    private static final int max = xxx.length() << 3;
    private static int i = 0;
    private static void onGenerateIteration() {
        Core.setVarString("gi", xxx.substring(0, (++i)>>3 ));
        if (i >= max) i = 0;
        if ((i & 7) == 0 )
            CommandQueue.add("refresh");
    }
    /********************************* *****************************************/

	static RSAKey create(int keyLength ) throws InterruptedException
	{

		BigInteger p, q, n, d;

		Random rnd = new Random();

		makeSmallPrimes();


		p = new BigInteger( rnd, keyLength / 8 / 4 / 2 );
		while( true )
		{
			//we need 256 bits.
			p.setZeroBit();
			p.orHighWord( 0x80000000 );
			if( !p.divides( EXP_VALUE ) && isProbablePrime( p ) )
			{
				break;
			}
			p.regenerate( rnd );
//HungLM
//            Security.onGenerateIteration();

		}

		q = new BigInteger( rnd, keyLength / 8 / 4 / 2 );
		while( true )
		{
			q.setZeroBit();
			q.orHighWord( 0x80000000 );
			//now q.BIT_LENGTH == 256
			n = BigInteger.times( p, q );

			if( n.bitLength() == keyLength && isProbablePrime( q ) && !q.divides( EXP_VALUE ) )
			{
				break;
			}
			q.regenerate( rnd );
                        //HungLM
//            Security.onGenerateIteration();
		}

		deleteSmallPrimes();

		System.gc();
		BigInteger phi = BigInteger.times( p.subtractOne(), q.subtractOne() );
		d = pub.modInverse( phi );

		return new RSAKey( n, d );
	}
}
